package com.beck.bee.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Created by cdliubei@jd.com on 4/5/2017.
 */
public class DistinctSubsequences115 {

    public static void main(String[] args) {

    }

    public int numDistinct(String S, String T) {
        if(S == null || T==null) {
            return 0;
        }
        if(S.length()<T.length()) {
            return 0;
        }
        //递推公式用的
        int [][] dp = new int[S.length()+1][T.length()+1];
        dp[0][0] = 1;
        //任意一个字符串变换成一个空串都只有一种变换方法
        for(int i=0;i<S.length();i++) {
            dp[i][0] = 1;
        }
        //递推公式
        for(int i=1;i<=S.length();i++) {
            for(int j=1;j<=T.length();j++) {
                //如果S和T的当前字符相等，那么有两种选法；否则S的当前字符不能要
                dp[i][j] = dp[i-1][j];
                if(S.charAt(i-1)==T.charAt(j-1)) {
                    dp[i][j] += dp[i-1][j-1];
                }
            }
        }
        return dp[S.length()][T.length()];
    }

    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (numRows <= 0)
            return result;

        ArrayList<Integer> pre = new ArrayList<Integer>();
        pre.add(1);
        result.add(pre);

        for (int i = 2; i <= numRows; i++) {
            ArrayList<Integer> cur = new ArrayList<Integer>();

            cur.add(1); //first
            for (int j = 0; j < pre.size() - 1; j++) {
                cur.add(pre.get(j) + pre.get(j + 1)); //middle
            }
            cur.add(1);//last

            result.add(cur);
            pre = cur;
        }

        return result;
    }

    public   int  maxProfit(int [] prices) {
        int min = Integer.MAX_VALUE,max=0;
        for (int i=0;i<prices.length;i++){
            min=Math.min(min,prices[i]);
            max=Math.max(max,prices[i]-min);
        }
        return max;
    }

    public int ladderLength(String start, String end, List<String> dict) {
        if(start==null || end==null || start.length()==0 || end.length()==0 || start.length()!=end.length())
            return 0;

        LinkedList<String> wordQueue = new LinkedList<String>();
        int level = 1; //the start string already count for 1
        int curnum = 1;//the candidate num on current level
        int nextnum = 0;//counter for next level

        wordQueue.add(start);

        while(!wordQueue.isEmpty()){
            String word = wordQueue.poll();
            curnum--;

            for(int i = 0; i < word.length(); i++){
                char[] wordunit = word.toCharArray();
                for(char j = 'a'; j <= 'z'; j++){
                    wordunit[i] = j;
                    String temp = new String(wordunit);

                    if(temp.equals(end))
                        return level+1;
                    if(dict.contains(temp)){
                        wordQueue.add(temp);
                        nextnum++;
                        dict.remove(temp);
                    }
                }
            }

            if(curnum == 0){
                curnum = nextnum;
                nextnum = 0;
                level++;
            }
        }

        return 0;
    }

}
